package com.algorithm.ch1.cjm.other;

/**
 * 缺失数字
 * 给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。
 *
 * @Author: Jie Ming Chen
 * @Date: 2018/9/16
 * @Version 1.0
 */
public class MissingNumber {

    public static void main(String[] args) {

        int[] nums = new int[]{3, 0, 1};
        new MissingNumber().missingNumber(nums);
    }

    /**
     * 求出最大值， 1 到最大值的和 减去 数组的和
     * @param nums
     * @return
     */
    public int missingNumber(int[] nums) {

        if (nums == null) {
            return 0;
        } else if (nums.length == 0) {
            return 0;
        }

        int index = 0;
        int sum = 0;
        int max = nums[0];
        while (index < nums.length) {
            sum += nums[index];

            if (max < nums[index]) {
                max = nums[index];
            }
            index ++;
        }

        if (max != nums.length) {
            return max + 1;
        }

        int i = 1;
        int total = 0;
        while (i <= max) {
            total += i;
            i ++;
        }

        int res = total - sum;

        return res;
    }
}
